package com.huffmantreecode;


import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        //数组中存放了字符串中每个字符的ASCII编码
        //byte[] bytes = str.getBytes();
//        //字符串转字符数组 toCharArray()
        char[] chars = str.toCharArray();
        byte[] zip = huffmanZip(chars);
//        System.out.println(Arrays.toString(zip));
        char[] decode = decode(huffmanCode, zip);
        for(char c :decode){
            System.out.print(c+" ");
        }


    }

    /**
     * 统计每个字符出现的次数，将字符-次数存放在结点中，返回结点的集合
     */
    public static List<Node> getNode(char[] chars){
        ArrayList<Node> nodes = new ArrayList<>();
        //统计每个字符出现的次数
        Map<Character,Integer> counts = new HashMap<>();
        for(char c:chars){
            Integer count = counts.get(c);
            if(count == null){
                counts.put(c,1);
            }else{
                counts.put(c,count+1);
            }
        }
        //转换成结点进行存储
        for(Map.Entry<Character,Integer> entry:counts.entrySet()){
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    /**
     * 构建赫夫曼树，返回树的根结点
     */
    public static Node createHuffmanTree(List<Node> nodes){
        while(nodes.size() != 1){
            Collections.sort(nodes);
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //创建的父节点只有权值weight，没有数据data
            //并且连接左右结点
            Node parent = new Node(null,leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.add(parent);
            nodes.remove(leftNode);
            nodes.remove(rightNode);
        }
        return nodes.get(0);
    }

    /**
     * 赫夫曼树前序遍历
     */
    public static void preOrder(Node root){
        if(root == null){
            System.out.println("该树为空树，不能遍历");
        }else {
            root.preOrder();
        }
    }
    //Map用于存放字符对应的赫夫曼编码
    static Map<Character,String> huffmanCode = new HashMap<>();
    //StringBuilder用于拼接编码，在
    //static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 将传入的node结点的所有叶子结点的赫夫曼编码得到，并保存在Map中
     */
    /*
    public static void getCodes(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        //先判断当前结点是否为空结点
        if(node != null){
            if(node.data == null){
                //非叶子结点则进行左右递归，先扫描右子树，再扫描左子树
                getCodes(node.left,"0",stringBuilder2);
                getCodes(node.right,"1",stringBuilder2);
            }else {
                //该节点为叶子结点，即存放了对应的字符
                huffmanCode.put(node.data,stringBuilder2.toString());
            }
        }
    }
    */
    public static void getCodes(Node node,String str){
        //先判断当前结点是否为空结点
        if(node != null){
            if(node.data == null){
                //非叶子结点则进行左右递归，先扫描右子树，再扫描左子树
                getCodes(node.left,str.concat("0"));
                getCodes(node.right,str.concat("1"));
            }else {
                //该节点为叶子结点，即存放了对应的字符
                huffmanCode.put(node.data,str);
            }
        }
    }

    public static void getHuffmanCodes(Node root){
        getCodes(root,"");
    }

    /**
     * 将得到的赫夫曼编码对字符数组中的字符进行替换
     * 替换后每八位为一组作为补码求其原码，并将该二进制原码装换成十进制来压缩存放在byte数组中，将byte数组发送
     */
    public static byte[] zip(char[] chars,Map<Character,String> huffmanCode){
        StringBuilder stringBuilder = new StringBuilder();
        for(char c: chars){
            stringBuilder.append(huffmanCode.get(c));
        }
        //定义byte数组的长度，如果被8整除，商为长度
        //不被8整除，len = 商 + 1
        int len = (stringBuilder.length()+7)/8;
        byte huffmanCodeByte[] = new byte[len];
        String code = "";
        int index = 0;
        //遍历StringBuilder，每8位为1组，步长为8
        for(int i = 0 ; i< stringBuilder.length();i+=8){
            if(i+8>stringBuilder.length()){
                //StringBuilder中的子串长度不足8
                code = stringBuilder.substring(i);
            }else {
                //subString 左开右闭
                code = stringBuilder.substring(i,i+8);
            }
           huffmanCodeByte[index++] = (byte) Integer.parseInt(code,2);
        }
        return huffmanCodeByte;
    }

    /**
     * 赫夫曼编码相关方法封装
     */
    public static byte[] huffmanZip(char[] chars){
        List<Node> node = getNode(chars);
        Node root = createHuffmanTree(node);
        //preOrder(root);
        getHuffmanCodes(root);
        byte[] zip = zip(chars, huffmanCode);
        return zip;
    }

    /**
     * 将一个byte转换成二进制的字符串
     * @param flag 是否需要补高位，true表示需要补高位，false表示无序补高位
     *             正数在通常情况下需要补高位，补齐8位
     *             但如果数为最后一个数时，无需补齐高位，直接转换
     */
    public static String byteToString(byte b,boolean flag){
        int temp = b;
        if(flag){
            temp |= 256;
        }
        /*
        如果传入正数，需要对少的位进行补齐，即将temp与256进行或运算
        如2 = 01, 256 = 1 0000 0000, 01 | 1 0000 0000 = 1 0000 0010, 取后八位
        如果传入的数为负数，取补码的高8位，如-2 -> 11111111111111111111111111111110, 取后八位
        */

        String str = Integer.toBinaryString(temp);
        if(flag){
            return str.substring(str.length()-8);
        }else {
            return str;
        }

    }

    /**
     * 按照赫夫曼编码，对压缩的数据进行解码
     * @param huffmanCode 存放字符对应的赫夫曼编码
     * @param huffmanBytes 转换后的编码
     * @return
     */
    public static char[] decode(Map<Character,String> huffmanCode,byte[] huffmanBytes){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0;i<huffmanBytes.length;i++){
            //byte最后一个元素不需要补齐八位
            boolean flag = (i != huffmanBytes.length-1);
            String str = byteToString(huffmanBytes[i], flag);
            stringBuilder.append(str);
        }
        //根据赫夫曼编码转换成对应的字符，huffmanCode中key为字符，value为编码
        //因为Map中，一个key对应一个value，而相同的value可能对应几个key，所以不能直接通过value找key
        //根据编码找字符，需要将原本的huffmanCode反转
        HashMap<String,Character> reversCode = new HashMap<>();
        for(Map.Entry<Character,String> entry:huffmanCode.entrySet()){
            reversCode.put(entry.getValue(),entry.getKey());
        }
        //存放扫描的结果
        List<Character> list = new ArrayList<>();
        //定义双指针，扫描stringBuilder中的编码字符，还原成原本的字符串
        for(int i =0;i<stringBuilder.length();){
            //i表示从第i位开始扫描,count表示每次扫描的位数,如果和reversCode中的字符匹配，加入到集合中，并下次i=i+count;
            int count = 1;
            //匹配到reversCode中对应的元素后，结束遍历
            boolean flag = true;
            Character c = null;
            while(flag){
                String key = stringBuilder.substring(i,i+count);
                c = reversCode.get(key);
                if(c == null){
                    count++;
                }else {
                    flag = false;
                }
            }
            list.add(c);
            i+=count;
        }
        //for循环结束以后，集合中就包含所有的字符
        //最后将list中的数据放入Char[]数组中并返回
        char[] chars = new char[list.size()];
        for(int i = 0;i<list.size();i++){
            chars[i] = list.get(i);
        }
        return chars;
    }
}
